This application is based upon and claims the benefit of priority from the prior Japanese Patent Applications No. 11-371560, filed Dec. 27, 1999; and No. 2000-195895, filed Jun. 29, 2000, the entire contents of which are incorporated herein by reference.
This invention relates to a data control system and a data rearrangement method. More particularly, the present invention relates to a disk control system using a log-structured write-in scheme and a data rearrangement method applicable to such a system.
In recent years, computer systems provided with a RAID (redundant array of independent disks) feature are in the main stream. Various types of RAID technology are known to date and they include the 0, 1, 10 and 5 types.
Recently, log-structured file systems (LSFS) have been proposed to improve the write-in performance of a RAID. The log-structured file system represents a technique for improving the performance of a RAID by utilizing the characteristic property of a disk unit that xe2x80x9cthe sequential access is by far faster than the random accessxe2x80x9d. The fall in the efficiency of a computer system during a random access process is attributable to the time consumed for a seek operation and in waiting for a rotary motion of the disk and hence such a fall of efficiency is desirably eliminated. Thus, with the log-structured file system technology, a buffer is used to store the data, and the data to be written into a plurality of small blocks are transformed into a large mass of data to be written by section of a technique of xe2x80x9cbatch writingxe2x80x9d for writing data in a batch. With this technique, an operation of randomly writing data is changed to an operation of sequentially writing data to improve the writing performance of the system.
However, with the log-structured file system technology, the data to be written are rearranged according to the order of the write requests issued for the data. Therefore, once random writing occurs, data with logical addresses that are widely separated from each other are consecutively written in a single physical stripe region. As a result, data blocks with consecutive logical addresses of a file system are stored in different physical stripe regions that are physically remote from each other. Then, the operation of sequentially reading the data stored in physically dispersed regions is in fact physically a random reading operation and hence is poorly efficient.
The data to be written have to be rearranged periodically in order to correct such a situation and make the data to be physically continuously arranged. However, the operation of rearranging the data represents a heavy load to the system that involves many I/O processing operations.
It is an object of the present invention to provide a disk control system and a data rearrangement method that are adapted to efficiently rearrange data and greatly improve the efficiency of data reading operations with a small load applied to the system.
According to the present invention, there is provided a disk control system using a log-structured write-in scheme and adapted to store data to be written in a buffer and write a plurality of data blocks, which are stored in the buffer, in a disk unit in unit of one physical stripe formed of a continuous storage region of the disk unit, the disk control system comprising a data rearrangement section configured to rearrange the data written in the disk unit in units of one block so as to make data with consecutive logical addresses to be written physically consecutively, a rearrangement stripe determination section configured to computationally determines at least one of a percentage of valid blocks and a percentage of the consecutive logical address numbers of adjacently located logical blocks in each physical stripe and determining the physical stripes to be reconstructed by the data rearrangement section as objects of rearrangement.
With a disk control system having the above configuration, the percentage of valid blocks and/or the percentage of the consecutive logical address numbers of adjacently located logical blocks is computationally determined for each physical stripe and the physical stripes to be rearranged by the data rearrangement section as objects of rearrangement are selected on the basis of the outcome of the computation. Since a physical stripe showing a low percentage of valid blocks is wasting the disk capacity, such a physical stripe should be selected with priority as object of rearrangement. A physical stripe showing a low percentage of valid blocks can be reused as empty stripe by processing it for data rearrangement. Additionally, a physical stripe containing valid blocks to a certain extent that are not arranged consecutively does not provide a high efficiency for a sequential read operation. Then, the efficiency of sequential read operation can be improved by selecting such a physical stripe as object of rearrangement.
In the present invention, when data rearrangement processing is executed, the necessity of carrying out a data rearrangement operation is determined for the physical stripes in the order of time and date of generation and the physical stripe with the oldest time and date of generation is selected as object of data rearrangement with priority. From the viewpoint of locality of file systems, a physical stripe whose time and date of generation is old can be assumed to contain valid blocks that are hardly selected as objects of rewriting. The frequency of occurrence of a new writing operation can be minimized for the data collected by data rearrangement and hence operations of ineffective rearrangement can be prevented from taking place by carrying out a data rearrangement operation for physical stripes whose time and date of generation is old.
The data rearrangement operation of the data rearrangement section is executed each time when a physical stripe is selected by the rearrangement stripe determination section as object of rearrangement. With this arrangement, the operation of computationally determining the percentage of valid blocks and/or the percentage of the consecutive logical addresses of adjacently located blocks for the next physical stripe is conducted after the completion of the operation of rearrangement for the current physical stripe selected as object of rearrangement so that the percentage of valid blocks and/or the percentage of the consecutive logical addresses of adjacently located blocks can be determined accurately by taking the invalid blocks into consideration.
A disk control system as defined above additionally comprises a management section which controls the number of times of references to any of the data contained in each physical stripe, the rearrangement stripe determination section being adapted to determine a physical stripe showing a number of times of references per unit time above a predetermined value as object of rearrangement with priority. With this arrangement of selecting data blocks that are frequently read with priority to arrange its physical storage regions continuously, the reading performance of the system can be remarkably improved.
Alternatively, a disk control system as defined above may additionally comprise a computation section which obtains an aggregate of valid blocks contained in the selected physical stripe for each of the logical stripe numbers allocated to the valid blocks on the basis of the logical addresses of the valid blocks and computing the number of elements of the aggregate having the largest number out of the aggregates formed by the section, the rearrangement stripe determination section being adapted to determine a physical stripe showing a number of elements as determined by the computation below a predetermined value as object of rearrangement with priority. Generally, data can be accessed at high speed for reading if they are not arranged consecutively in a rigorous sense of the word but found physically close to each other. Therefore, it is desirable to rearrange a physical stripe showing a low degree of concentration of data with priority by determining the degree of concentration of each physical stripe by means of the above described technique.
When the physical stripe data rearranged on the empty region of the disk device are batch-written in the disk unit, the data rearrangement section generates data of the physical stripe by block data belonging to an identical logical stripe number contained in the physical stripe to be rearranged and remaining block data belonging to the logical stripe number collected from the other physical stripe other than the physical stripe to be rearranged.
In such a manner, by aggregating the blocks in a new physical stripe in units of the aggregate of the logical blocks, the data blocks in the physical blocks to be rearranged can be rearranged en masse in an optimum state. As a result, it is avoided in the rearrangement processing to move the same logical block at a plurality of times, so that the efficiency of the rearrangement processing is improved.
Then, the data rearrangement section arranges the data blocks of the new physical stripe in the order of logical block number to improve the efficiency of sequentially reading the blocks.
The data blocks of a physical stripe generated very recently can be selected frequently as object of write operation. Then, if such data blocks are moved for rearrangement, they may be moved again to some other physical stripe as a result of a subsequent write operation to make the initial move ineffective. Therefore, preferably, the data rearrangement section excludes the blocks of a physical stripe having a life time not longer than a predetermined value since the generation from the objects of the collection for rearrangement.
A disk control system as defined above further comprises an additional rearrangement section which rearranges the physical stripes showing a percentage of the consecutive logical addresses of adjacently located blocks not smaller than a predetermined value on a physical stripe by physical stripe basis. With this arrangement, it is possible to establish continuity of data blocks in terms of boundaries of physical stripes.
According to the present invention, there is provided a disk control system using a log-structured write-in scheme, the disk control system comprising a disk array constructed by a plurality of disk units, a data buffer which stores a plurality of data blocks requested to be written, a data write-in section which generates to-be-written data corresponding to a physical stripe allocated to the disk array out of the plurality of data blocks stored in the data buffer and writes them collectively in the physical stripe, an address conversion table which stores, for each logical stripe, correspondence relations between a plurality of block numbers of a plurality of logical blocks of the logical stripe of the disk array and a plurality of physical block numbers indicating the physical positions on the disk array at which the data blocks specified by the logical block numbers exist, rearrangement stripe determination section which computes at least one of a percentage of valid logical blocks on the logical stripe and a percentage of consecutive physical address numbers on the logical blocks to obtain a result, and determines the logical stripe as object of rearrangement when the result satisfies a predetermined condition, a data rearrangement section which reads out the data blocks of the logical stripe determined by the rearrangement stripe determination section as object of rearrangement and causes the data write-in section to write them in an empty physical stripe region of the disk array, and an address conversion table rewriting section which rewrites the physical block numbers of the address conversion table as physical block numbers of the empty physical stripe.
With such a disk control system, the extent of physical dispersion of logical blocks can be determined for each logical stripe by referring to the address conversion table. More specifically, for each logical stripe, the system determines the percentage of valid logical block numbers and/or the percentage of the consecutive logical address numbers of adjacently located logical blocks in the logical stripe and determines the logical stripe as object of rearrangement when the obtained result satisfies predetermined conditions. Logical stripes showing a low percentage of valid logical block numbers are preferably excluded from the objects of rearrangement because no remarkable effect can be expected if such logical stripes are rearranged. Additionally, the efficiency of sequentially reading logical stripes that contain valid logical blocks to a certain extent but show a poor consecutiveness of physical block numbers is rather poor and hence the efficiency of sequential read can be improved by selecting the data blocks of such logical stripes as objects of rearrangement.
According to the present invention, there is also provided a disk control system using a log-structured write-in scheme, the disk control system comprising a disk array constructed by a plurality of disk units, a data buffer which stores a plurality of data blocks requested to be written, a data write-in section which generates to-be-written data corresponding to a physical stripe allocated to the disk array out of the plurality of data blocks stored in the data buffer and writes them collectively in the predetermined physical stripe of the disk array, an address conversion table which stores, for each logical stripe, correspondence relations between a plurality of logical block numbers of a plurality of logical blocks of the logical stripe of the disk array and a physical block numbers indicating the physical positions on the disk array at which the data blocks specified by the logical block numbers exist, a counter section arranged for each logical stripe of a logical stripe management table and adapted to count the number of times of data reads for the logical blocks contained in the logical stripe, a rearrangement stripe determination section which determines the logical stripe showing a number of times of data reads not smaller than a predetermined value as object of rearrangement by referring to the counter section, a data rearrangement section which reads out the data blocks of the logical stripe determined by the rearrangement stripe determination section as object of rearrangement and causes the data write-in section to write them in an empty physical stripe region of the disk array, and an address conversion table rewriting section which rewrites the physical block numbers of the address conversion table as physical block numbers of the empty physical stripe.
With this arrangement, a logical stripe show a large number of times of data reads is selected as object of data rearrangement so that the data blocks in the logical stripe that is frequently read can be arranged physically consecutively to raise the efficiency of sequential reading.
According to the present invention, there is also provided a disk control system using a log-structured write-in scheme, the disk control system comprising a disk array constructed by a plurality of disk units, a data buffer which stores a plurality of data blocks requested to be written, a data write-in section which generates data to be written for a physical stripe of the disk array out of the plurality of data blocks stored in the data buffer and writes them collectively in the predetermined physical stripe of the disk array, an address conversion table which stores for each logical stripe the correspondence between the plurality of logical block numbers of the logical stripe of the disk array and the physical block numbers indicating the physical positions on the disk array of the data blocks specified by the logical block numbers, a counter section arranged for each logical stripe of a logical stripe management table and adapted to count the number of times of data write-ins for the logical blocks contained in the logical stripe, a rearrangement stripe determination section which determines the logical stripe showing a number of times of data write-ins not smaller than a predetermined value as object of rearrangement by referring to the counter section, a data rearrangement section which reads out the data blocks of the logical stripe determined by the rearrangement stripe determination section as object of rearrangement and causes the data write-in section to write them in an empty physical stripe region of the disk array, and an address conversion table rewriting section which rewrites the physical block numbers of the address conversion table as physical block numbers of the empty physical stripe.
A logical stripe can become physically discontinuous when data is written in any of its logical blocks. Therefore, the efficiency of sequential access can be improved effectively by selecting logical stripes showing a number of times of data write-ins not smaller than a predetermined value as objects of rearrangement.
According to the present invention, there is provided a data rearrangement method to be applied to a control system using a log-structured write-in scheme and adapted to store data in a buffer and write the plurality of blocks, which stored in the buffer, in a disk unit in units of one physical stripe formed of a continuous storage region of the disk unit, the data rearrangement method comprising steps of rearranging the data written in the disk unit in units of one block so as to make data with consecutive logical addresses to be written physically consecutively, and computationally determining at least one of a percentage of valid blocks and a percentage of the consecutive logical address numbers of adjacently located logical blocks in each physical stripe and determining the physical stripes to be reconstructed in the data rearranging step as objects of rearrangement.
According to the present invention, there is provided data rearrangement method to be applied to a control system using a log-structured write-in scheme and adapted to store data in a buffer and write the plurality of blocks, which are stored in the buffer, in a disk unit in units of one physical stripe formed of a continuous storage region of the disk unit, the data rearrangement method comprising steps of determining the physical stripe as object of rearrangement, and rearranging the data written in the disk unit in units of one block so as to make data with consecutive logical addresses to be written physically consecutively, when the physical stripe data rearranged on the empty region of the disk unit are batch-written in the disk unit, the data rearrangement step including generating data of the physical stripe by block data belonging to an identical logical stripe number contained in the physical stripe to be rearranged and remaining block data belonging to the logical stripe number collected from the other physical stripe other than the physical stripe to be rearranged.
According to the present invention, there is provided a data rearrangement method for rearranging the data blocks stored in a disk array comprising a plurality of disk units, the method comprising steps of storing a plurality of data blocks requested to be written in a data buffer, generating data to be written for a physical stripe of the disk array out of the plurality of data blocks stored in the data buffer, writing them collectively in a predetermined physical stripe of the disk array, generating an address conversion table for storing for each logical stripe the correspondence between the plurality of logical block numbers of the logical stripe of the disk array and the physical block numbers indicating the physical positions on the disk array of the data blocks specified by the logical block numbers, counting the number of times of data reads for the logical blocks contained in each logical stripe, determining the logical stripe showing a number of times of data reads not smaller than a predetermined value as object of rearrangement by referring to the counting step, rearranging data by reading out the data blocks of the logical stripe determined as object of rearrangement, writing them in the empty physical stripe region of the disk array produced by the collectively writing step, and rewriting the physical block numbers of the address conversion table as physical block numbers of the empty physical stripe as a result of the data rearrangement.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.